package com.dragon.app.practice;

import java.util.Arrays;

public class Sort {

    public Sort() {
    }

    public void Sort() {
    }

    public static void main(String[] args) {
        int[] arr = new int[]{42, 86, 4, 64, 1, 76, 543, 33, 86, 508, -29, 0, -11, 523, 645, 657, 3, 45, 141, 64565, 6758, 64500, 9897846, 23, 13};


//        insertionSort(arr);
//        insertionSort2(arr);
//        selectionSort(arr);
//        selectionSort2(arr);
//        bubbleSort(arr);
//        quickSort(arr, 0, arr.length - 1);
        quickSort2(arr, 0, arr.length - 1);


        System.out.println(Arrays.toString(arr));
    }

    /**
     * 直接 插入排序
     *
     * @param values
     * @return
     */
    public static int[] insertionSort(int[] values) {
        int temp = 0;

        // 默认第一个数据是有序数组，所以从第二个数据开始取要插入的数据
        for (int i = 1; i < values.length; i++) {
            temp = values[i];
            int j = i;
            for (; j > 0; j--) {
                if (temp < values[j - 1]) {
                    values[j] = values[j - 1];
                } else {
                    break;
                }
            }
            values[j] = temp;
        }

        return values;
    }

    /**
     * 直接 插入排序 第二次写
     *
     * @param values
     * @return
     */
    public static int[] insertionSort2(int[] values) {
        int temp = 0;

        for (int i = 1; i < values.length; i++) {
            temp = values[i];
            for (int j = i; j > 0; j--) {
                if (values[j - 1] <= temp) {
                    break;
                }
                values[j] = values[j - 1];
                values[j - 1] = temp;
            }
        }

        return values;
    }

    /**
     * 直接 选择排序
     *
     * @param values
     * @return
     */
    public static int[] selectionSort(int[] values) {
        int temp = 0;

        for (int i = 0; i < values.length - 1; i++) { // 做第i趟选择
            int k = i;
            for (int j = k + 1; j < values.length; j++) { // 选最小的记录
                if (values[j] < values[k]) {
                    k = j; // 记下目前找到的最小值所在的位置
                }
            }
            // 在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
            if (i != k) {
                temp = values[i];
                values[i] = values[k];
                values[k] = temp;
            }
        }

        return values;
    }

    /**
     * 直接 选择排序 第二次写
     *
     * @param values
     * @return
     */
    public static int[] selectionSort2(int[] values) {
        int temp = 0;

        for (int i = 0; i < values.length - 1; i++) {
            int min = i;
            for (int j = i; j < values.length; j++) {
                if (values[j] < values[min]) {
                    min = j;
                }
            }
            temp = values[i];
            values[i] = values[min];
            values[min] = temp;
        }

        return values;
    }

    /**
     * 交换排序——冒泡排序
     *
     * @param values
     * @return
     */
    public static int[] bubbleSort(int[] values) {
        int temp = 0;
        boolean out = true;

        for (int i = 0; i < values.length - 1; ++i) {
            for (int j = 0; j < values.length - 1 - i; ++j) {
                if (values[j] > values[j + 1]) {
                    temp = values[j];
                    values[j] = values[j + 1];
                    values[j + 1] = temp;
                    out = false;
                }
            }
            if (out) {
                break;
            }
        }

        return values;
    }


    /**
     * 交换排序——快速排序
     * 拆东墙补西墙，拆西墙补东墙。
     *
     * @param values
     * @param _left：左边界
     * @param _right：右边界
     */
    public static int[] quickSort(int values[], int _left, int _right) {
        int left = _left;
        int right = _right;
        int temp = 0;

        if (left < right) { // 待排序的元素至少有两个的情况
            temp = values[left]; // 待排序的第一个元素作为基准元素
            while (left < right) { // 从左右两边交替扫描，直到left = right
                while (left < right && values[right] >= temp) {
                    right--; // 从右往左扫描，找到第一个比基准元素小的元素
                }
                values[left] = values[right]; // 找到这种元素arr[right]后与arr[left]交换
                while (left < right && values[left] <= temp) {
                    left++; // 从左往右扫描，找到第一个比基准元素大的元素
                }
                values[right] = values[left]; // 找到这种元素arr[left]后，与arr[right]交换
            }
            values[right] = temp; // 基准元素归位
            quickSort(values, _left, left - 1); // 对基准元素左边的元素进行递归排序
            quickSort(values, right + 1, _right); // 对基准元素右边的元素进行递归排序
        }

        return values;
    }

    /**
     * 交换排序——快速排序 第二次写
     * 拆东墙补西墙，拆西墙补东墙。
     *
     * @param values
     * @param _left：左边界
     * @param _right：右边界
     */
    public static int[] quickSort2(int values[], int _left, int _right) {

        if (_left < _right) {
            int left = _left;
            int right = _right;
            int temp = values[_left];  //选取第一个元素为基准元素
            while (left < right) {
                for (; left < right; right--) {
                    if (values[right] < temp) {
                        values[left] = values[right];
                        left++;
                        break;
                    }
                }
                for (; left < right; left++) {
                    if (values[left] > temp) {
                        values[right] = values[left];
                        right--;
                        break;
                    }
                }
            }
            values[left] = temp;  //基准元素归位
            quickSort2(values, _left, left - 1);
            quickSort2(values, right + 1, _right);
        }

        return values;
    }


}
